/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        234.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/14 20:01
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//请判断一个链表是否为回文链表。
#include "../header.h"

class Solution {
public:
//    bool isPalindrome(ListNode* head) {
//        left = head;
//        return traverse(head);
//    }
//
//private:
//    ListNode *left;
//    bool traverse(ListNode *right){
//        if (right == nullptr) return true;
//        bool ans = traverse(right->next);
//        ans = ans && (left->val == right->val);
//        left = left->next;
//        return ans;
//    }
    bool isPalindrome(ListNode *head) {
        if (head == nullptr)
            return true;
        ListNode *fast, *slow;
        slow = fast = head;
        ListNode *p, *q;
        while (fast != nullptr && fast->next != nullptr) {
            p = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        if (fast != nullptr) {
            p = slow;
            slow = slow->next;
        }
        ListNode *right = reverse(slow);
        q = right;
        ListNode *left = head;
        while (right != nullptr) {
            if (right->val != left->val)
                return false;
            right = right->next;
            left = left->next;
        }
        p->next = reverse(q);
        return true;
    }

private:
    ListNode *reverse(ListNode *head) {
        ListNode *pre = nullptr, *cur, *next;
        cur = next = head;
        while (cur != nullptr) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};